#include<stdlib.h>
#include<stdio.h>
#define MAXN 15
int N=15,k=5;
int data[MAXN] = {14,3,13,1,16,4,10,5,2,11,9,8,12,7,15};
int s[8] = {4,3,13,2,16,1,10,5};

void kbig(int left,int right){
    int pivot,num;
    pivot = partition(left,right);
    num = pivot + 1;
    if(num > k){
        kbig(left,pivot-1);
    }
    else if(num < k){
        k -= num;
        kbig(pivot+1,right);
    }
    else
        return;
}

int partition(int left,int right){
    int x,pivot,i,j,t;
    x = data[right];
    i=left-1,j=left;
    for(;j<=right-1;j++){
        if(data[j]>x){
            i++;
            t = data[i];
            data[i] = data[j];
            data[j] = t;
        }
    }
    t = data[right];
    data[right] = data[i+1];
    data[i+1] = t;
    return i+1;
}

void validate(){
    int i,num=0,x=data[4];
    for(i=0;i<N;i++)
        if(data[i]<=x)
            num++;
    for(i=0;i<N;i++)
        printf(" %d",data[i]);
}

int main(){
    int i,num;
    kbig(0,N-1);
    validate();
    return 0;
}
